package String.easy;

import java.util.HashMap;

/**
 * 1. 问题描述
 *        给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。
 *        如果不存在这样的子字符串，返回 -1 。子字符串 是字符串中的一个连续字符序列。
 *
 * 2. 算法分析
 *      1. 穷举法
 *          把所有的情况找出来，从里面找到做大长度即可 (时间复杂度非常高，内存消耗也比较大，只是思维难度小，代码好些)
 *
 *      2. 实际上如果两个相同字符靠的越远，之间的长度就会越大，如果这两个字符之间的还存在相同字符
 *         那么他们之间的长度一定不是最大的，所以就没有必有找，故我们只需要找到第一对相同字符，我们
 *         设置两个指针i = 0；j = len-1；一个指向s的头部，一个指向s的尾部。i向增加的方向遍历，j
 *         向减少的方向遍历
 *
 *         我们先采用一个hashmap来记录s中每个字符出现的下标
 *
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 两个相同字符之间的最长子字符串 {
    public static void main(String[] args) {
        System.out.println(maxLengthBetweenEqualCharacters3("aa"));
    }

    /**
     * 穷举法实现
     * @param s
     * @return
     */
    public static int maxLengthBetweenEqualCharacters1(String s) {
        int len = s.length();
        if (len == 0 || len == 1) {return -1;}
        int maxLength = 0; // 记录最大长度
        boolean flag = false; // 记录s是否存在相同的字符
        for (int i = 0; i < len; i++) {
            for (int j = len-1; j > i; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    flag = true;
                    maxLength = Math.max(maxLength,j-i-1);
                    break; // 第一次找到的就是最优解 添加上这一句之后和算法实现2的思想是一摸一样的
                }
            }
        }
        return (maxLength == 0 && flag == false) ? -1 : maxLength;
    }

    /**
     *  与上述类似，但是时间复杂度还是很高，稍微强了一点  30%
     *  遇上述不同之处在于上述是将所有的情况都判断了一遍，但是这个一旦遇到最优解，就停止了遍历
     *  这个最优解也非常好理解：所谓的最长宽度就是需要两个相同的字符尽可能靠近两端，所以相同字符
     *  之间的情况我们不需要考虑，因为肯定不会是最长的宽度，这就是该算法对于上述的一种优化
     * @param s
     * @return
     */
    public static int maxLengthBetweenEqualCharacters2(String s) {
        if (s.length() == 0 || s.length() == 1) {return -1;}
        int first = 0;
        int last = s.length() - 1;
        int max = -1;
        for (int i = first;i < last;i++) {
            for (int j = last; j > i;j--) {
                if (s.charAt(i) != s.charAt(j)) {
                    continue;
                }
                max = Math.max(max,j-i-1);
                break;
            }
        }
        if (max>=0) {return max;}
        return -1;
    }

    /**
     * 上述两种方法的时间平均时间复杂度都比较高
     *
     * 我们使用一个数组 pos 来记录每个字符在26个字母中出现的位置 实际上就是 char - 'a'来计算
     * 相同字符的位置应该相同，当我们遍历s是，当前的的字符为char则在数组中对应的索引为char-'a'
     * 则
     *
     * 时间复杂度为O(n) n为字符串的长度 ，内存消耗仅仅是使用了一个长度为26的pos数组
     *
     * @param s
     * @return
     */
    public static int maxLengthBetweenEqualCharacters3(String s) {
        int[] pos = new int[26]; // 默认每个位置上的值为0
        // 初始化pos
        for (int i = 0; i < pos.length; i++) {
            pos[i] = -1; // 初始化的目的：如果pos的默认值为0如果出现aa这样的字符串遍历完pos之后整个pos数组不变，因为a对应在26字母中的索引就是0
        }
        int max = -1; //  初始化为-1(表明当前s中没有重复字符)
        for (int i = 0; i < s.length(); i++) {
            // 获取当前字符在数组pos的索引
            int idx = s.charAt(i) - 'a';
            // 判断当前获取的idx的位置上是是否有值，如果没有说明该字符是第一次出现，如果有则是重复出现的
            if (pos[idx] == -1) {
                // 当前字符是第一次出现
                pos[idx] = i; // 数组的第idx位置记录的是当前字符在s中的索引位置
            } else {
                // 当前字符不是第一次出现，比较当前字符和，
                // 我们需要计算出当前字符与之前出现的相同的字符之间的间隔大小并于当前的max比较，用较大的一个更新max
                max = Math.max(max,i-pos[idx]-1); // pos[idx]为当前字符第一次出现的位置
            }
        }
        return  max;
    }
}
